home *** CD-ROM | disk | FTP | other *** search
/ Amiga Plus 1995 #1 / Amiga Plus 1995 #1.iso / fish-disketten / fish_761-770 / d765 / gambit_comp / repr < prev    next >
Text File  |  1994-12-13  |  12KB  |  299 lines
  1. Object representation specification for Gambit
  2. ----------------------------------------------
  3.  
  4. This document describes the object representation scheme that all Gambit
  5. back ends must support.
  6.  
  7.  
  8. 1. Abstract object representation
  9. ---------------------------------
  10.  
  11. Objects are encoded by (signed) integers.  It is required that the
  12. size of the encoding be the same as that for a C `long' (so that
  13. Scheme and C can interface easily).  A certain number of bits are
  14. allocated for each of 2 fields in encodings: the `data' and `type
  15. tag'.  The type tag determines which class the object belongs to out
  16. of 7 possible classes.  Thus, the type tag field must be at least 3
  17. bits wide.  Some of the objects are scalars (the encoding of a scalar
  18. is always the same), the others are known as memory allocated objects
  19. (a memory allocated object might have a different encoding after a GC
  20. because its encoding depends on its address).  The actual mapping of
  21. type tags to object classes is totally left to the implementor and can
  22. thus be different from machine to machine.
  23.  
  24. The 7 object classes are defined as follows:
  25.  
  26. Class        Objects represented
  27.  
  28. FIXNUM       small signed integers
  29. SPECIAL      characters, #t, #f, () and other special objects
  30. PAIR         cons cells
  31. WEAK_PAIR    'weak' cons cells (car is replaced by #f if not referenced)
  32. PLACEHOLDER  placeholders (returned by `future' special form)
  33. SUBTYPED     vectors, strings, symbols, flonums, ports, etc.
  34. PROCEDURE    procedures (includes true closures and return addresses)
  35.  
  36. The FIXNUM and SPECIAL classes are scalars.  The PAIR, WEAK_PAIR,
  37. SUBTYPED, PROCEDURE and PLACEHOLDER classes are memory allocated objects.
  38.  
  39. There are some restrictions to the representation of scalars.  The
  40. encoding of the fixnum `n' is required to have `n' in the data field
  41. (in 2s-complement representation).  This should make the
  42. implementation of fixnum arithmetic simple on most machines and also
  43. simplifies the interface to the object representation.  Additionally,
  44. the encoding of a character is required to have `n' in the data field,
  45. where `n' is the machine representation of the character and 0<=n<=255
  46. (i.e. the lower 8 bits of the data field are the machine
  47. representation of the character and the other data field bits are 0).
  48.  
  49. Also, in order to permit the creation of new scalars by the runtime or the
  50. user (e.g.  the introduction of an `end-of-file' object), there should
  51. be a reserved range of encodings in the SPECIAL class.  This range is
  52. back end dependent.
  53.  
  54. Some memory allocated objects have a header.  Headers are used to
  55. store length and subtype information.  PAIRS, WEAK_PAIRS and PLACEHOLDERS
  56. don't have a header because their length is fixed.  PAIRS and WEAK_PAIRS
  57. have two fields (the CAR and CDR).  PLACEHOLDERS have 4 fields (the VALUE,
  58. LOCK, THUNK and QUEUE).  The VALUE slot of placeholders must come first.
  59.  
  60. SUBTYPED objects have a header.  Headers are the same
  61. size as a C `long' and are always at the very beginning of the object.
  62. Headers contain two fields, the `length' and `subtype'.  The length
  63. corresponds to the length of the object in bytes (excluding the
  64. header).  The following is a list of the required subtypes:
  65.  
  66. VECTOR, SYMBOL, PORT, RATNUM, COMPNUM, STRING, BIGNUM, FLONUM
  67.  
  68. SUBTYPED objects are all vector-like.  They are subdivided into 2
  69. classes: object-vectors (those whose elements are objects) and
  70. byte-vectors (those that contain binary information).  The key
  71. difference between these is that the first type has to be scanned by
  72. the GC and the second doesn't.  There must be reserved ranges of
  73. subtypes for the creation of both new object-vector and byte-vector
  74. object types.  These ranges are back end dependent.
  75.  
  76. Closures (i.e. special PROCEDURE objects) have two parts.  The first
  77. part contains binary data that is not scanned by the GC.  The second
  78. part holds the closed variables of the closure and is thus scanned by
  79. the GC.  The length of the first part is constant and is back end
  80. dependent.
  81.  
  82.  
  83. 2. Notes on implementation
  84. --------------------------
  85.  
  86. The abstract representation leaves a certain amount of freedom to the
  87. implementor so that representation decisions can be tailored to each
  88. target machine.  What follows is a sample implementation for the M68000.
  89.  
  90. First of all, we can choose encodings to be 32 bits wide (the length of
  91. a C `long'), using the lower 3 bits for the type tag and the upper
  92. 29 for the data field.
  93.  
  94. We can then elect to allocate memory allocated objects at addresses that
  95. are multiples of 8.  This should not waste too much memory as pairs
  96. neatly fit in 8 bytes and 2 bytes are wasted on the average per
  97. object-vector.  The address of a memory allocated object thus has the 3
  98. bits `000' in the type field.  The encoding of memory allocated objects
  99. can thus be the address of the start of the object plus the type tag
  100. in the lower 3 bits.  This has the advantage that no addressing range
  101. is lost and the address of a slot in an object can be computed simply
  102. by adding an offset to the object encoding.
  103.  
  104. We can also be clever in the selection of the type tags.  For example,
  105. we could choose the following:
  106.  
  107. 000 FIXNUM        001 WEAK_PAIR     010 PROCEDURE     011 SUBTYPED
  108. 100 PAIR          101 PLACEHOLDER   110 not used      111 SPECIAL
  109.  
  110. The advantages of this mapping are:
  111.  
  112.   1) Fixnum arithmetic is very simple.  For addition and substraction,
  113.      just add or substract the encodings themselves.  Multiplication
  114.      and division require a single extra shift by 3.
  115.  
  116.   2) Pairs can be represented as: CDR followed by CAR.  This means that
  117.      the encoding of a pair is the address of the CAR of the pair.
  118.      Thus, `address register indirect' addressing can be used to access
  119.      the CAR and `address register indirect with predecrement' addressing
  120.      can be used to access the CDR.  Both of these are efficient
  121.      addressing modes on the M68000.
  122.  
  123.   3) Type tags can be tested in a single instruction.  This is done with
  124.      a `btst' (bit-test) instruction and a couple of data registers that
  125.      contain masks.  For example, if register d1 must be tested for
  126.      `pair?' and register d7 always contains the `pair mask' value
  127.      11101111111011111110111111101111, then the instruction sequence
  128.  
  129.         btst d1,d7
  130.         beq  xxx
  131.  
  132.      will jump to `xxx' if register d1 is a pair.  The mask for
  133.      placeholders is 11011111110111111101111111011111.  Note that these
  134.      two values are in fact valid encodings of SPECIAL objects and we
  135.      could choose:
  136.  
  137.         pair mask        = encoding of #f
  138.         placeholder mask = encoding of ()
  139.  
  140.      Tests for `falseness' and `null?' would then be very efficient if
  141.      these two masks are in fact kept in registers.
  142.  
  143.   4) If the entry point of procedures is at an offset of 2 off of the
  144.      start of the procedure object then jumps to procedures can be
  145.      performed by a direct jump to the encoding of the procedure.  This
  146.      respects the M68000 restriction that only even addresses can be jumped
  147.      to.  Note that this will require careful alignment of the procedure
  148.      entry points (and return addresses which are also `procedures') to
  149.      addresses having 010 in the lower 3 bits.
  150.  
  151.   5) The format of SUBTYPED objects can be defined as:
  152.  
  153.                                upper 24 bits       lower 8 bits
  154.         start of     +---------+---------+---------+---------+
  155.         object   --> |   length of data in bytes   | subtype |  header
  156.                      +---------+---------+---------+---------+
  157.                      |  object 0    (or first 4 bytes)       | \
  158.                      +---------------------------------------+ |
  159.                      |  object 1    (or next 4 bytes)        | | data
  160.                      +---------------------------------------+ |
  161.                      | ...                                   | /
  162.                      +---------------------------------------+
  163.                       <-------------- 32 bits -------------->
  164.  
  165.      where `subtype' = n*8 with `n' in the range 0..15 for object-vectors
  166.      and in the range 16..31 for byte-vectors.  It is then fairly easy to get
  167.      the subtype and the length information.  The encoding of a SUBTYPED
  168.      object is the address of the subtype information so `address register
  169.      indirect' addressing can be used to get the subtype.  The length of an
  170.      object-vector (in fixnum format) is the header shifted right by 7.
  171.      For a byte vector, a shift of 5 followed by a resetting of the lower
  172.      3 bits to 0 is needed.
  173.  
  174. Similar implementation tricks can be used for other machines to take
  175. advantage of their architecture and instruction set.
  176.  
  177.  
  178. 3. Interface to the object representation
  179. -----------------------------------------
  180.  
  181. The interface to the object representation is defined through global
  182. variable bindings that all back ends must have.  Some of these
  183. bindings are to procedures (which we will call primitives).
  184. The primitives described are not expected to check for error
  185. conditions (e.g. type and bounds checks).  The names of the global
  186. variables used are prefixed by `##' so that they reside in a different
  187. name space than the identifiers available to the user.
  188.  
  189.  
  190. Miscellaneous
  191.  
  192.   (##NOT x)                 #t if x is false, else #f
  193.  
  194.   (##EQ? x y)               #t if encoding of x and y are the same, else #f
  195.  
  196.  
  197. Type tags
  198.  
  199.   (##TYPE obj)              Returns the fixnum equal to type tag of `obj'.
  200.                             E.g. (##type "") --> SUBTYPED type tag.
  201.  
  202.   (##TYPE-CAST obj tag)     Returns the `data' field of `obj' with `tag'
  203.                             in the `type tag' field.
  204.                             E.g. (##type-cast x (##type 0)) --> fixnum
  205.                             equal to data field part of encoding of x.
  206.                             Notice that it is safe to convert a memory
  207.                             allocated object into a scalar type, but
  208.                             generally not the reverse.
  209.  
  210.  
  211. Subtype tags
  212.  
  213.   (##SUBTYPE obj)           Returns fixnum equal to subtype tag of SUBTYPED
  214.                             object `obj'.
  215.                             E.g. (##subtype "hi") --> subtype of strings.
  216.  
  217.   (##SUBTYPE-SET! obj tag)  Changes the subtype of the SUBTYPED object `obj'
  218.                             to `tag' and returns `obj'.
  219.  
  220.  
  221. Pairs and weak pairs
  222.  
  223.   (##CONS x y)              Same as (cons x y).
  224.   (##SET-CAR! x val)        Same as (set-car! x val) but returns `x'.
  225.   (##SET-CDR! x val)        Same as (set-cdr! x val) but returns `x'.
  226.   (##CAR x)                 Same as (car x).
  227.   (##CDR x)                 Same as (cdr x).
  228.  
  229.   (##WEAK-CONS x y)         Similar but for weak pairs
  230.   (##WEAK-SET-CAR! x val)   
  231.   (##WEAK-SET-CDR! x val)   
  232.   (##WEAK-CAR x)            
  233.   (##WEAK-CDR x)            
  234.  
  235.  
  236. Object vectors
  237.  
  238.   (##MAKE-VECTOR n val)     Same as (make-vector n val).
  239.   (##VECTOR-LENGTH x)       Same as (vector-length x).
  240.   (##VECTOR-REF x i)        Same as (vector-ref x i).
  241.   (##VECTOR-SET! x i val)   Same as (vector-set! x i val) but returns `x'.
  242.   (##VECTOR-SHRINK! x n)    Shrinks length of object-vector `x' to `n'
  243.                             and returns `x'.
  244.  
  245.  
  246. Byte vectors
  247.  
  248.   (##MAKE-STRING n val)     Same as (make-string n val).
  249.   (##STRING-LENGTH x)       Same as (string-length x).
  250.   (##STRING-REF x i)        Same as (string-ref x i).
  251.   (##STRING-SET! x i val)   Same as (string-set! x i val) but returns `x'.
  252.   (##STRING-SHRINK! x n)    Shrinks length of byte-vector `x' to `n'
  253.                             and returns `x'.
  254.  
  255.  
  256. Fixnums
  257.  
  258. (numeric arguments and results are fixnums)
  259.  
  260.   (##FIXNUM.+ x...)
  261.   (##FIXNUM.* x...)
  262.   (##FIXNUM.- x y...)
  263.   (##FIXNUM.QUOTIENT x y)   
  264.  
  265.   (##FIXNUM.= x...)
  266.   (##FIXNUM.< x...)
  267.  
  268.  
  269. Flonums
  270.  
  271. (numeric arguments and results are flonums)
  272.  
  273.   (##FLONUM.+ x...)
  274.   (##FLONUM.* x...)
  275.   (##FLONUM.- x y...)
  276.   (##FLONUM./ x y...)
  277.  
  278.   (##FLONUM.= x...)
  279.   (##FLONUM.< x...)
  280.  
  281.  
  282. Procedures
  283.  
  284.   (##APPLY p args)
  285.   (##CALL-WITH-CURRENT-CONTINUATION p)
  286.  
  287.  
  288. Placeholders
  289.  
  290.   (##TOUCH x)  Return `x' if it is not a placeholder, otherwise
  291.                wait until value of `x' is known and return it.
  292.  
  293.  
  294. Interpreter related
  295.  
  296.   (##GLOBAL-VAR name)            Return index of global var. `name'
  297.   (##GLOBAL-VAR-REF index)       Reference a global var. using its index
  298.   (##GLOBAL-VAR-SET! index val)  Assign value to a global var. using its index
  299.